#include <vector>
#include <algorithm>
using namespace std;
/*
 * @lc app=leetcode.cn id=16 lang=cpp
 *
 * [16] 最接近的三数之和
 */

// @lc code=start
class Solution {
public:
    // -4 -1 1 2
    int threeSumClosest(vector<int>& nums, int target) {
        int res = -1;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, e = nums.size() - 1;
            while (l < e) {
                int t = nums[i] + nums[l] + nums[e];
                if (t == target) return target;
                else if (t > target) e--;
                else l++;
                if (res == -1 || abs(res - target) > abs(t - target))
                    res = t;
            }
        }
        return res;
    }
        
};
// @lc code=end

